<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Maximum Subsquare With Sides as X</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="maximum-subsquare-with-sides-as-x">Maximum Subsquare With Sides as X</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=vi_1eHCsR9A&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=41">https://www.youtube.com/watch?v=vi_1eHCsR9A&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=41</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/SubsquareSurrounedByXs.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/SubsquareSurrounedByXs.java</a></li>
</ul>
<p>给定一个矩阵matrix，只包含&quot;X&quot; 和 &quot;O&quot; 元素， 求其中一个最大的子正方形， 边界全部是&quot;X&quot;元素. 返回这个最大的子正方形的边长</p>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp17.png" alt="dp17.png"></p>
<p>解决思路就是计算一个dp矩阵，dp[i][j]表示以matrix[i][j]元素结尾，在垂直方向上的最大连续&quot;X&quot;长度， 和在水平方向上的最大连续&quot;X&quot;长度</p>
<p>然后逐个遍历dp[i][j], 以上图中的dp[4][4] = (5,3) 为例， 意味着以 (4,4)为右下角的所求正方形最大可能的边长是3</p>
<ol>
<li>假设所求正方形边长是3， 那么往左看， dp[4,2] = (4,1) 符合条件, 但是往上看, dp[2,4] = (3,1) 就不符合条件了。</li>
<li>假设所求正方形边长是2， 那么往左看， dp[4,3] = (2,2) 符合条件， 往上看， dp[3,4] = (4,5) 也如何条件。</li>
</ol>
<p>最后以 (4,4) 为右下角的所求正方形最大可能的边长是2,   像这样挨个遍历所有位置，可以求得最大符合条件的正方形边长是3</p>

    </body>
    </html>